|
|
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (advisor) ; Nešetřil, Jaroslav (referee)
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
|
|
|
Automorphism Groups of Geometrically Represented Graphs
Zeman, Peter ; Klavík, Pavel (advisor) ; Nedela, Roman (referee)
In this thesis, we are interested in automorphism groups of classes of graphs with a very strong structure. Probably the first nontrivial result in this direction is from 1869 due to Jordan. He gave a characterization of the class T of the automorphism groups of trees. Surprisingly, automorphism groups of intersection-defined classes of graphs were studied only briefly. Even for deeply studied classes of intersection graphs the structure of their automorphism groups is not well known. We study the problem of reconstruct- ing the automorphism group of a geometric intersection graph from a good knowledge of the structure of its representations. We mainly deal with interval graphs. Interval graphs are intersection graphs of intervals on the real line. They are one of the oldest and most studied classes of geometric intersection graphs. Our main result is that the class T is the same as the class I of the automorphism groups of interval graphs. Moreover, we show for an interval graph how to find a tree with the same automorphism group, and vice versa. 1
|
|
|
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (advisor) ; Nešetřil, Jaroslav (referee)
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
|
|
|
Automorphism Groups of Geometrically Represented Graphs
Zeman, Peter ; Klavík, Pavel (advisor) ; Nedela, Roman (referee)
In this thesis, we are interested in automorphism groups of classes of graphs with a very strong structure. Probably the first nontrivial result in this direction is from 1869 due to Jordan. He gave a characterization of the class T of the automorphism groups of trees. Surprisingly, automorphism groups of intersection-defined classes of graphs were studied only briefly. Even for deeply studied classes of intersection graphs the structure of their automorphism groups is not well known. We study the problem of reconstruct- ing the automorphism group of a geometric intersection graph from a good knowledge of the structure of its representations. We mainly deal with interval graphs. Interval graphs are intersection graphs of intervals on the real line. They are one of the oldest and most studied classes of geometric intersection graphs. Our main result is that the class T is the same as the class I of the automorphism groups of interval graphs. Moreover, we show for an interval graph how to find a tree with the same automorphism group, and vice versa. 1
|
|
|
Évariste Galois and his theory
Richter, Lukáš ; Kvasz, Ladislav (advisor) ; Jančařík, Antonín (referee)
TITLE: Évariste Galois and His Theory AUTHOR: Lukáš Richter DEPARTMENT: The Department of Mathematics and Teaching of Mathematics SUPERVISOR: prof. RNDr. Ladislav Kvasz, Dr. ABSTRACT: The first part of my thesis deals with the life of the significant French mathematician of the 19th century, Évariste Galois, the founder of modern algebra. It is focused on his school years, meetings with mathematics, unsuccessful entrance exams to university, expulsion from school, his mathematic works and his bad experiences with French Academy of Science. He had difficulties with law during his life twice, he was judged and imprisoned. At the end of his short life he fell in love unhappily and consequently was killed in a duel. The second part is devoted to the solution of polynomial equations of the first degree up to the fourth degree by the algebraic patters already known at the times of Galois. Each of the formula is derived by the method suitable even for the students of secondary schools and its usage is illustrated on the example. The third part contains the basics of the Galois Theory and the insolubility of polynomial equations of at least fifth degree is demonstrated. Some of the statements are introduced on examples. KEYWORDS: Évariste Galois, polynomial equations, field extensions, automorphism groups, Galois Theory
|
guest ::
